package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-06-27 17:30
 */
public class 题库_0130_被围绕的区域 {
/*
[
["X","O","X","O","X","O"],
["O","X","O","X","O","X"],
["X","O","X","O","X","O"],
["O","X","O","X","O","X"]
]

[
["X","O","X","O","X","X"],
["O","X","X","X","X","X"],
["X","X","X","X","X","X"],
["O","X","O","X","X","X"]
]

 */


  public static void main(String[] args) {
    char[][] board = {
        {'X', 'O', 'X', 'O', 'X', 'O'},
        {'O', 'X', 'O', 'X', 'O', 'X'},
        {'X', 'O', 'X', 'O', 'X', 'O'},
        {'O', 'X', 'O', 'X', 'O', 'X'},
    };

    Solution solution = new Solution();
    solution.solve(board);
  }

  static
  class Solution {

    private final int[][] nexts = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    public void solve(char[][] board) {
      if (board == null || board.length == 0 || board[0] == null || board[0].length == 0) {
        return;
      }

      boolean[][] mark = new boolean[board.length][board[0].length];
      // 第一列 和 最后一列
      for (int i = 0; i < board.length; ++i) {
        dfs(board, i, 0, mark);
        dfs(board, i , board[0].length - 1, mark);
      }
      // 第一行 和 最后一行
      for (int j = 0; j < board[0].length; ++j) {
        dfs(board, 0, j, mark);
        dfs(board, board.length - 1, j, mark);
      }

      for (int i = 0; i < board.length; ++i) {
        for (int j = 0; j < board[0].length; ++j) {
          if (!mark[i][j]) {
            board[i][j] = 'X';
          }
        }
      }

    }

    private void dfs(char[][] board, int x, int y, boolean[][] mark) {
      if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] == 'X' || mark[x][y]) {
        return;
      }
      mark[x][y] = true;
      for (int[] next : nexts) {
        dfs(board, x + next[0], y + next[1], mark);
      }

    }

  }

}
